package com.example.leetcode.top145;

/**
 * @author: dangwen
 * @createDate: 2022/4/20
 */
public class Test {

    public static void main(String[] args) {
        int[] arr = new int[]{45, 80, 55, 40, 42, 85};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    static void quickSort(int[] arr, int left, int right){
        if (right <= left){
            return;
        }
        int low = left, high = right, pivot = arr[low];
        while (low < high){
            while (low < high && arr[high] >= pivot){
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot){
                low ++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        quickSort(arr, left, low - 1);
        quickSort(arr, low + 1, right);

    }

//    public static void quickSort(int[] arr, int start, int end) {
//        if (end <= start) {
//            return;
//        }
//        int low = start;
//        int high = end;
//        int pivot = arr[low];
//        while (low < high) {
//            while (low < high && arr[high] >= pivot) {
//                high--;
//            }
//            arr[low] = arr[high]; // 将小于 pivot 的数放在地位
//            while (low < high && arr[low] <= pivot) {
//                low++;
//            }
//            arr[high] = arr[low]; // 将大于 pivot 的数放在高位
//        }
//        arr[low] = pivot;
//        quickSort(arr, start, low - 1); // 递归排序左半部分
//        quickSort(arr, low + 1, end); // 递归排序右半部分
//    }
}
